1. Field of the Invention
This invention generally relates to an arbiter circuit, and in particular to an arbiter circuit for processing concurrent requests made at random times by a plurality of digital subsystems for the use of shared resources.
2. Description of the Prior Art
In a multiple system such as a multiprocessor system, a plurality of subsystems, for example, central processing units which operate independently of one another share some resources such as a disc storage device, demands for the use of the shared resources are made at random times, often concurrently, by the sharing subsystems, making it necessary to process those concurrent requests. For example, one subsystem may make a request for the permission to use the shared resource when it is currently being accessed by another subsystem. In this situation, the late-to-come demand must be temporarily suspended until the current subsystem has completed its use of the shared resource. The arbiter circuit is one typical device for processing the coexisting demands, and is disclosed, for example, in an article by T. Sakurai et al entitled, "A 36ns 1 Mbit Pseudo SRAM with VSRAM Mode." (Digest of Technical Papers for the 1987 Symposium on VLSI Circuits, May 22, 1987, pp. 45)
In order to have a brief background understanding of the invention, reference is made to FIG. 1 which illustrates in block diagram a prior-art arbiter circuit. Digital subsystems 1a and 1b in a multiprocessor system operate independently of each other with no operative interrelations, and hence generate at random times request signals REQ-A and REQ-B for demanding the use of a shared resource 3 in the form of a disc storage device. The request signals REQ-A and REQ-B are supplied to an arbiter circuit 2, which in turn provides an acknowledgement signal ACK-A or another acknowledgement signal ACK-B to the shared resource 3, the ACK-A signal indicating the request by the REQ-A signal has been acknowledged, whereas the ACK-B signal representing the request by the REQ-B signal has been granted.
To state in more detail, the arbiter circuit 2 includes a first NAND gate 2a which is supplied with the REQ-A signal and ACK-B signal, and produces the ACK-A signal. Also included in the arbiter circuit 2 is a second NAND gate 2b which is supplied with the REQ-B signal and the ACK-A signal, and operates to generate the ACK-B signal. In essence, the arbiter circuit 2 is an SR flip-flop composed of the first and second NAND gates 2a and 2b.
Now, the operation of the arbiter circuit of FIG. 1 is described with reference to FIG. 2 which shows a series of waveforms as they appear at various points in the circuit.
Under an operating situation where both the subsystem 1a and the subsystem 1b are silent on the demand for access to the shared resource with the request signals REQ-A and REQ-B being at "L" level, one input of the first NAND gate 2a to be supplied with the REQ-A signal is kept at the "L" level, and the output signal ACK-A of the same NAND gate takes on a high or "H" level regardless of the signal level or state the ACK-B signal assumed at the output of the second NAND gate 2b, and thus at the other input of the first NAND gate 2a. With the REQ-B signal at one input of the second NAND gate 2b also being at the "L" level, the ACK-B signal at the output of the second NAND gate 2b is at the "H" level regardless of the level which the ACK-A signal at the other input of the second NAND gate takes. The request acknowledgement signals ACK-A and ACK-B are low-level acting, the presence of the high-level acknowledgement signals ACK-A and ACK-B at time t.sub.0 in FIG. 2 indicates that the arbiter circuit 2 fails to acknowledge any request for the use of the shared resource by the REQ-A and REQ-B signals.
At time t.sub.1 when the subsystem 1a presents the request for permission to use the shared resource 3 while the subsystem 1b is silent on a similar request, one request signal REQ-A shifts to the high logic level or state, whereas the other request signal REQ-B remains at the low logic level. Under the conditions, both inputs of the first NAND gate 2a are applied with high-level signals, causing the NAND gate 2a to generate a low-level acknowledgement signal ACK-A at its output. This indicates that the request made by the signal REQ-A has been granted. Meanwhile, with a low-level REQ-B signal being applied to its one input, the second NAND gate 2b provides a high-level ACK-B signal at its output, indicating that no request is acknowledged by the second NAND gate 2b. When the subsystem 1a is through with the use of the shared resource, the request signal REQ-A falls back to its low logic level, followed instantly by the ACK-A signal returning to its high logic level.
Further, at time t.sub.2 when the subsystem 1b makes a request for permission to use the shared resource 3 with the other subsystem 1a silent on such request, the request signal REQ-B for the subsystem 1b changes from the low logic level to the high logic level, while the request signal REQ-A for the subsystem 1a stays at the low logic level. Under the conditions, the second NAND gate 2b has high-level signals applied to both its inputs, and thus produces a low-level ACK-B signal at the output, indicating that the request by the REQ-B signal has been acknowledged. On the other hand, the first NAND gate 2a, with the low-level REQ-A signal being supplied at one input, generates a high-level ACK-A signal at the output, representing the absence of a request from the subsystem 1a. Upon the completion of the use of the shared resource by the subsystem 1b, the request signal REQ-B shifts back to the low logic level accompanied by the ACK-B signal returning to the high logic level or state.
Now to consider a situation where two requests are made in a time-staggered manner. At time t.sub.3, the subsystem 1a produces a high-level request signal REQ-A asking for access to the shared resource 3, upon the receipt of which the first NAND gate 2a provides a low-level ACK-A signal to grant the request. Subsequent to the first request by the subsystem 1a, the subsystem 1b issues a second request for the use of the same shared resource 3 by providing a high-level REQ-B signal to the one input of the second NAND gate 2b at time t.sub.4. It is noted that, at this point, the second NAND gate 2b is being supplied at the other input with the low-level ACK-A signal from the output of the first NAND gate 2a. Thus, the application of the second high-level request signal REQ-B to the second NAND gate 2b in no way affects the ACK-B signal currently in its high logic state at the output of the second NAND gate. With the ACK-B signal at the high logic level, the second NAND gate 2b does not accept the second request made by the subsystem 1b.
When the subsystem 1a vacates the shared resource 3 at time t.sub.5, the request signal REQ-A shifts down to the low logic level, causing the ACK-A signal at the output of the first NAND gate 2a to return to the high logic level. The request by the subsystem 1a is thus negated. The other request made by the subsystem 1b is still valid with the high level REQ-B signal applied to the one input of the second NAND gate, the emergence of the high-level ACK-B signal at the output of the first NAND gate 2a applies another high-level signal to the other input of the second NAND gate 2b. As a result, the ACK-B signal at the output of the second NAND gate shifts to the low logic level to put the request by the signal REQ-B into effect. When this request by the subsystem 1b is brought to an end, the ACK-B signal again moves back to the high logic level as before.
In short, if the subsystem 1a and 1b make individual requests for access to the shared resource 3 at different points of time, the arbiter circuit 2 functions to accept the earlier request into effect, while suspending the later request until the earlier one has been fully implemented.
However, the prior-art arbiter circuit of FIG. 1 is incapable of coping with two concurrent requests made by both subsystem 1a and 1b at a time. Now to consider a case where the request signals REQ-A and REQ-B are simultaneously shifted from the low level to the high level at time t.sub.6, just prior to this time when both signals REQ-A and REQ-B are at the low levels, the acknowledgement signals ACK-A and ACK-B are in their high logic state. Under the circumstances, the simultaneous shifting of the REQ-A and REQ-B signals into the high logic states drives the ACK-A output of the first NAND gate 2a into the low level on one hand since the first NAND gate has been supplied with the high level ACK-B signal at the one input. It also drives the ACK-B output signal of the second NAND gate 2b toward the low logic level because the second NAND gate has been supplied with the high-level ACK-A signal at the one input. Since the arbiter circuit 2 is essentially an SR flip-flop, the simultaneous application of the high level signals REQ-A and REQ-B to the arbiter circuit leads to the generation of the ACK-A and ACK-B output signals with the opposite logic levels. Consequently, the ACK-A and ACK-B signals which are shifting from the high level to the low level counter act with each other to drive the other signal toward the high level. The overall result is that both the ACK-A signal and the ACK-B signal are forced to "stay afloat" midway between the high and low logic levels. With the acknowledgement signals midway between the prescribed logic levels or states, there are good chances that the arbiter circuit is unable to process the concurrent demands and neither of the requesting subsystems are denied access to the shared resource. This in turn may contribute to an undesirable consequence of faulty operation in the multiprocessing system.